package BackTracking.combination;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

class combine {

    /**
     * 组合问题，有顺序要求
     * */
    public static List<List<Integer>> combine(int n, int k, List<List<Integer>> res) {
        List<Integer> inner = new ArrayList<>();
        dfs(n,k,1,inner,res);
        return res;


    }

    static void dfs(int n, int k, int start, List<Integer> inner, List<List<Integer>> res){

        if(inner.size()==k){
            res.add(new ArrayList<>(inner));
            return;
        }
        // 1-n总共可以选n次，for循环为第一次选择的元素有n种可能性
        /**剪枝优化
         * 组合的顺序要求，当选择第一个元素的位置后的元素数量已经不够k时，就没必要进行运算了
         *  比如 n为6  k=3，当选1时符合要求，因为后面有5个可以选，但当第一个选到5时，就可以停了，因为5后面只有6且个数肯定不满足
         *  所以，可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。
         *  inner.size()是已经选择的数量，k-inner.size是还需要的数量
         *  在集合n中至多要从该起始位置 : n - (k-inner.size) + 1，开始遍历
         * */
        for (int i = start; i <= n - (k-inner.size()) + 1; ++i) {
            inner.add(i);
            //且组合有顺序要求，因此选中第一个元素后，剩下的元素只能在之后中选择
            dfs(n,k,i+1,inner,res);
            inner.remove(inner.size()-1);  //回溯
        }
    }

    public static void main(String[] args) {
        List<List<Integer>> res = new ArrayList<>();
        combine(4,2, res);
        for (List<Integer> r:res
             ) {
            System.out.println(r);
        }
    }

}
